| 【算法】字典序超详细解析（让你有一种相见恨晚的感觉！） | 您所在的位置：网站首页 › 字典 in single › 【算法】字典序超详细解析（让你有一种相见恨晚的感觉！） |
【算法】字典序超详细解析（让你有一种相见恨晚的感觉！）
|
目录 一、前言 二、什么是字典序 ？ ✨字典序概念 ✨深度理解字典序 ✨字典序排序的重要性和应用场景 三、常考面试题 ✨ 下一个排列 ✨ 字典数排序 ✨ 字典序最小回文串 四、共勉 一、前言经常刷算法题的朋友，肯定会经常看到题目中提到 字典序 这样的字眼，或者需要我们通过字典序来解题，由于之前对字典序了解的不太清楚，导致做题的时候总会卡住，所以收集了一些资料来详解字典序。 二、什么是字典序 ？ ✨字典序概念字典序（dictionary order），又称 字母序（alphabetical order），含义是表示英文单词在字典中的先后顺序，在计算机领域中扩展成两个任意字符串的大小关系。 举例： 在字典中，单词是按照首字母在字母表中的顺序进行排列的，比如 alpha 在 beta 之前。而第一个字母相同时，会去比较两个单词的第二个字母在字母表中的顺序，比如 account 在 advanced 之前，以此类推。下列单词就是按照字典序进行排列的： as aster astrolabe astronomy astrophysics at ataman attack baa ✨深度理解字典序 在学习 字符串string 的时候，我们肯定接触过两个字符串之间的比较，比如”abc“ < “acb” < “acbd”, 其规则是先比较第一个字母，如果不相等，就直接得到结果，如果相等，就比较下一个字母。如果两个字符串的长度不相等，但是长的那个字符串包含了短的那个，那长的那个字符串更大（比如"acb" < “acbd”）在我们进行比较之前，有一个默认的排序规则，就是‘a' < 'b' < 'c' < ... < 'z'举例： 对数字 【1，2，3，4，5，6，7，8，9，10，11，12，13】 按照字典序排列： 结果为 ：【1，10，11，12，13，2，3，4，5，6，7，8，9】总结： 对于两个不同的字符串，从左到右逐个比较它们的字符， 如果在某个位置上它们的字符不同，则将它们按照该位置上的字符的字母顺序进行排序，即较小的字符排在前面，较大的字符排在后面。如果一直比较到其中一个字符串结束，则较短的字符串排在前面；如果两个字符串完全相同，则它们的字典序相同。可以将它们看作是按照字母表的顺序进行排列的。 ✨字典序排序的重要性和应用场景 数据库索引：在数据库中，使用字典序排序可以加快查询速度。例如，对存储了字符串数据的列进行字典序排序，可以使得数据库在执行字符串比较操作时更高效。字符串比较：在字符串比较场景中，字典序排序能够方便地判断两个字符串的大小关系。例如，在编程中，可以使用字典序排序来实现字符串的字母顺序排序、查找最大/最小字符串等操作。文件系统排序：文件系统通常使用字典序排序来显示文件和目录的顺序。这样可以使得用户在文件浏览器中更容易找到特定的文件或目录。 三、常考面试题通过上面的讲解，相信大家应该对 字典序 有了一个基础的了解，想要深刻的理解它，还是需要通过题目来理解。 ✨ 下一个排列链接：31. 下一个排列 - 力扣（LeetCode）
题目分析： 说实话刚看题目我看了半天不知道在说什么，看到评论里面提到字典序算法才知道题意。我们拿题目中的例子1,2,3 ------> 1,3,2来说明： 首先本题讨论的范围是数字，数字中有一个规则，就是’0‘ < '1' < '2' < ... < '9',这与上面的a~z是一样的然后就是1，2，3这三个数字，我们能够形成6种不同的组合，即123 < 132 < 213 < 231 < 312 < 321。OK，如果你看懂前面两点，本题已经完成了。我们要做的就是找到当前数 123 在第二点的六种排列中间的下一个位置是什么，即 132，那么 132 就是答案如果要找的数字位于排列组合的最后一个一位，即 321，那么按照题目的第二行，我们就返回最小值 123.上面从直觉上理解了什么是字典序算法，下面说下怎么转化成程序算法。 何时无解 首先考虑无解情况，即上面所说的321，这种情况带入字典序算法是无解的，而321这种情况，如果我们单独拆分成3，2，1三个数字，其实是一个降序的过程： 因此如果当前排列是降序的，则字典序算法无解换而言之，如果不存在后一个数比前一个数大（20;i--) { if(nums[i]>nums[i-1]) { // 有解 flag = 1; // 初始化最小值 为右边断点 int min = nums[i],idx = i; // 向后找最小值 for(int j = i+1;j |
【本文地址】
公司简介
联系我们